package demo.practice.leetcode;


import java.util.LinkedList;

public class Offer54_2 {
    //https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/
    public static void main(String[] args) {
        Offer54_2 o= new Offer54_2();
        TreeNode r= new TreeNode(3);
        r.left= new TreeNode(1);
        r.right= new TreeNode(4);
        r.left.right= new TreeNode(2);

        TreeNode n = new TreeNode(5);
        n.left= new TreeNode(3);
        n.right= new TreeNode(6);
        n.left.right= new TreeNode(4);
        n.left.left= new TreeNode(2);
        n.left.left.left= new TreeNode(1);

        TreeNode e = new TreeNode(1);
        e.right= new TreeNode(2);

        int a=o.kthLargest(r,2);
        System.out.println(a);

    }

    LinkedList<Integer> list= new LinkedList<>();

    public int kthLargest(TreeNode root, int k) {
        foreach( root,k);
        return list.get(k-1);
    }

    private void foreach(TreeNode root,int k) {//前序遍历插入到list中
        if(root!=null){

            if (root.right!=null){
                foreach(root.right,k);
            }
            if(list.size()>=k)
                return;
            list.add(root.val);
            if (root.left!=null){
                foreach(root.left,k);
            }
        }
    }



}
